package com.lfg.leetcode.leetcode0;

import java.util.ArrayList;
import java.util.List;

public class No78subsets {

    public static void main(String[] args) {
        List<List<Integer>> ret = subsets(new int[]{1, 2, 3});
        System.out.println("[" + ret + "]");
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        boolean[] flag = new boolean[nums.length];
        List<Integer> data = new ArrayList<>(nums.length);
        subsets(0, nums, flag, ret, data);
        return ret;
    }

    public static void subsets(int index, int[] nums, boolean[] flag, List<List<Integer>> ret, List<Integer> data) {
        for (int j = index; j < nums.length; j++) {
            if (flag[j]) {
                continue;
            }
            flag[j] = true;
            data.add(nums[j]);
            ret.add(new ArrayList<Integer>(data));
            subsets(j + 1, nums, flag, ret, data);
            data.remove(data.size() - 1);
            flag[j] = false;
        }
    }
}

